package leetcode_题库;

import java.util.*;
import java.util.concurrent.atomic.AtomicInteger;

/**
 * Created by IntelliJ IDEA.
 *
 * @ProjectName leetcode
 * @Author Ding
 * @CreateTime 2022/8/23 15:31 星期二
 */
public class _387_字符串中的第一个唯一字符 {
    public static void main(String[] args) {

        System.err.println(firstUniqChar("leetcode"));

    }

    /**
     * 评论解法，比Map快了不少
     * > 2022/08/23 16:36:48
     * 解答成功:
     * 执行耗时:3 ms,击败了98.83% 的Java用户
     * 内存消耗:41.6 MB,击败了86.83% 的Java用户
     *
     * @param s
     * @return
     */
    public static int firstUniqChar(String s) {
        //将s转成char[]字符数组，多次使用charAt会降低效率
        char[] chars = s.toCharArray();
        //使用table，代替哈希表，存储题干要求的26个字符
        int[] table = new int[26];
        //计数
        for (char c : chars) {
            table[c - 'a']++;
        }
        //记录角标
        int i = 0;
        for (char c : chars) {
            //如果第c-'a'个元素的个数恰好是1，返回i
            if (table[c - 'a'] == 1) {
                return i;
            }
            //计数器累加
            i++;
        }
        return -1;
    }

    /**
     * 使用Map哈希表做的
     * > 2022/08/23 16:27:50
     * 解答成功:
     * 执行耗时:26 ms,击败了34.69% 的Java用户
     * 内存消耗:42.5 MB,击败了5.07% 的Java用户
     *
     * @param s
     * @return
     */
    public int firstUniqChar2(String s) {
        char[] chars = s.toCharArray();
        Map<Character, Integer> map = new LinkedHashMap<>(chars.length);

        for (char c : chars) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }

        int i = 0;
        for (char c : chars) {
            if (map.get(c) == 1) {
                return i;
            }
            i++;
        }
        return -1;
    }
}
